Graph Theory

• A1.8

  Graph Theory

  Part II, 2001

  (i) Show that any graph $G$ with minimal degree $\delta$ contains a cycle of length at least $\delta+1$. Give examples to show that, for each possible value of $\delta$, there is a graph with minimal degree $\delta$ but no cycle of length greater than $\delta+1$.

  (ii) Let $K_{N}$ be the complete graph with $N$ vertices labelled $v_{1}, v_{2}, \ldots, v_{N}$. Prove, from first principles, that there are $N^{N-2}$ different spanning trees in $K_{N}$. In how many of these spanning trees does the vertex $v_{1}$ have degree 1 ?

  A spanning tree in $K_{N}$ is chosen at random, with each of the $N^{N-2}$ trees being equally likely. Show that the average number of vertices of degree 1 in the random tree is approximately $N / e$ when $N$ is large.

  Find the average degree of vertices in the random tree.

  comment

• A2.8

  Graph Theory

  Part II, 2001

  (i) Prove that any graph $G$ drawn on a compact surface $S$ with negative Euler characteristic $E(S)$ has a vertex colouring that uses at most

  $$h=\left\lfloor\frac{1}{2}(7+\sqrt{49-24 E(S)})\right\rfloor$$

  colours.

  Briefly discuss whether the result is still true when $E(S) \geqslant 0$.

  (ii) Prove that a graph $G$ is $k$ edge-connected if and only if the removal of no set of less than $k$ edges from $G$ disconnects $G$.

  [If you use any form of Menger's theorem, you must prove it.]

  Let $G$ be a minimal example of a graph that requires $k+1$ colours for a vertex colouring. Show that $G$ must be $k$ edge-connected.

  comment

• A4.9

  Graph Theory

  Part II, 2001

  Write an essay on extremal graph theory. Your essay should include proofs of at least two major results and a discussion of variations on these results or their proofs.

  comment

• A1.8

  Graph Theory

  Part II, 2002

  (i) State and prove a necessary and sufficient condition for a graph to be Eulerian (that is, to have an Eulerian circuit).

  Prove that, given any connected non-Eulerian graph $G$, there is an Eulerian graph $H$ and a vertex $v \in H$ such that $G=H-v$.

  (ii) Let $G$ be a connected plane graph with $n$ vertices, $e$ edges and $f$ faces. Prove that $n-e+f=2$. Deduce that $e \leq g(n-2) /(g-2)$, where $g$ is the smallest face size.

  The crossing number $c(G)$ of a non-planar graph $G$ is the minimum number of edgecrossings needed when drawing the graph in the plane. (The crossing of three edges at the same point is not allowed.) Show that if $G$ has $n$ vertices and $e$ edges then $c(G) \geq e-3 n+6$. Find $c\left(K_{6}\right)$.

  comment

• A2.8

  Graph Theory

  Part II, 2002

  (i) Define the chromatic polynomial $p(G ; t)$ of the graph $G$, and establish the standard identity

  $$p(G ; t)=p(G-e ; t)-p(G / e ; t),$$

  where $e$ is an edge of $G$. Deduce that, if $G$ has $n$ vertices and $m$ edges, then

  $$p(G ; t)=a_{n} t^{n}-a_{n-1} t^{n-1}+a_{n-2} t^{n-2}+\ldots+(-1)^{n} a_{0},$$

  where $a_{n}=1, a_{n-1}=m$ and $a_{j} \geq 0$ for $0 \leq j \leq n$.

  (ii) Let $G$ and $p(G ; t)$ be as in Part (i). Show that if $G$ has $k$ components $G_{1}, \ldots, G_{k}$ then $p(G ; t)=\prod_{i=1}^{k} p\left(G_{i} ; t\right)$. Deduce that $a_{k}>0$ and $a_{j}=0$ for $0 \leq j<k$.

  Show that if $G$ is a tree then $p(G ; t)=t(t-1)^{n-1}$. Must the converse hold? Justify your answer.

  Show that if $p(G ; t)=p\left(T_{r}(n) ; t\right)$, where $T_{r}(n)$ is a Turán graph, then $G=T_{r}(n)$.

  comment

• A4.9

  Graph Theory

  Part II, 2002

  Write an essay on connectivity in graphs.

  Your essay should include proofs of at least two major theorems, along with a discussion of one or two significant corollaries.

  comment

• A1.8

  Graph Theory

  Part II, 2003

  (i) State Brooks' Theorem, and prove it in the case of a 3 -connected graph.

  (ii) Let $G$ be a bipartite graph, with vertex classes $X$ and $Y$, each of order $n$. If $G$ contains no cycle of length 4 show that

  $$e(G) \leqslant \frac{n}{2}(1+\sqrt{4 n-3})$$

  For which integers $n \leq 12$ are there examples where equality holds?

  comment

• A $2 . 8$,

  Graph Theory

  Part II, 2003

  (i) State and prove a result of Euler relating the number of vertices, edges and faces of a plane graph. Use this result to exhibit a non-planar graph.

  (ii) State the vertex form of Menger's Theorem and explain how it follows from an appropriate version of the Max-flow-min-cut Theorem. Let $k \geqslant 2$. Show that every $k$-connected graph of order at least $2 k$ contains a cycle of length at least $2 k$.

  comment

• A4.9

  Graph Theory

  Part II, 2003

  Write an essay on the vertex-colouring of graphs drawn on compact surfaces other than the sphere. You should include a proof of Heawood's bound, and an example of a surface for which this bound is not attained.

  comment

• A1.8

  Graph Theory

  Part II, 2004

  (i) Let $G$ be a connected graph of order $n \geq 3$ such that for any two vertices $x$ and $y$,

  $$d(x)+d(y) \geq k$$

  Show that if $k<n$ then $G$ has a path of length $k$, and if $k=n$ then $G$ is Hamiltonian.

  (ii) State and prove Hall's theorem.

  [If you use any form of Menger's theorem, you must state it clearly.]

  Let $G$ be a graph with directed edges. For $S \subset V(G)$, let

  $$\Gamma_{+}(S)=\{y \in V(G): x y \in E(G) \text { for some } x \in S\}$$

  Find a necessary and sufficient condition, in terms of the sizes of the sets $\Gamma_{+}(S)$, for the existence of a set $F \subset E(G)$ such that at every vertex there is exactly one incoming edge and exactly one outgoing edge belonging to $F$.

  comment

• A2.8

  Graph Theory

  Part II, 2004

  (i) State a result of Euler, relating the number of vertices, edges and faces of a plane graph. Show that if $G$ is a plane graph then $\chi(G) \leq 5$.

  (ii) Define the chromatic polynomial $p_{G}(t)$ of a graph $G$. Show that

  $$p_{G}(t)=t^{n}-a_{1} t^{n-1}+a_{2} t^{n-2}+\ldots+(-1)^{n} a_{n}$$

  where $a_{1}, \ldots, a_{n}$ are non-negative integers. Explain, with proof, how the chromatic polynomial is related to the number of vertices, edges and triangles in $G$. Show that if $C_{n}$ is a cycle of length $n \geq 3$, then

  $$p_{C_{n}}(t)=(t-1)^{n}+(-1)^{n}(t-1) .$$

  comment

• A4.9

  Graph Theory

  Part II, 2004

  Write an essay on trees. You should include a proof of Cayley's result on the number of labelled trees of order $n$.

  Let $G$ be a graph of order $n \geq 2$. Which of the following statements are equivalent to the statement that $G$ is a tree? Give a proof or counterexample in each case.

  (a) $G$ is acyclic and $e(G) \geq n-1$.

  (b) $G$ is connected and $e(G) \leq n-1$.

  (c) $G$ is connected, triangle-free and has at least two leaves.

  (d) $G$ has the same degree sequence as $T$, for some tree $T$.

  comment

• 1.II .17F

  Graph Theory

  Part II, 2005

  Show that an acyclic graph has a vertex of degree at most one. Prove that a tree (that is, a connected acyclic graph) of order $n$ has size $n-1$, and deduce that every connected graph of order $n$ and size $n-1$ is a tree.

  Let $T$ be a tree of order $t$. Show that if $G$ is a graph with $\delta(G) \geqslant t-1$ then $T$ is a subgraph of $G$, but that this need not happen if $\delta(G) \geqslant t-2$.

  comment

• 2.II.17F

  Graph Theory

  Part II, 2005

  Brooks' Theorem states that if $G$ is a connected graph then $\chi(G) \leqslant \Delta(G)$ unless $G$ is complete or is an odd cycle. Prove the theorem for 3-connected graphs $G$.

  Let $G$ be a graph, and let $d_{1}+d_{2}=\Delta(G)-1$. By considering a partition $V_{1}, V_{2}$ of $V(G)$ that minimizes the quantity $d_{2} e\left(G\left[V_{1}\right]\right)+d_{1} e\left(G\left[V_{2}\right]\right)$, show that there is a partition with $\Delta\left(G\left[V_{i}\right]\right) \leqslant d_{i}, i=1,2$.

  By taking $d_{1}=3$, show that if a graph $G$ contains no $K_{4}$ then $\chi(G) \leqslant \frac{3}{4} \Delta(G)+\frac{3}{2}$.

  comment

• 3.II.17F

  Graph Theory

  Part II, 2005

  Let $X$ and $Y$ be disjoint sets of $n \geqslant 6$ vertices each. Let $G$ be a bipartite graph formed by adding edges between $X$ and $Y$ randomly and independently with probability $p=1 / 100$. Let $e(U, V)$ be the number of edges of $G$ between the subsets $U \subset X$ and $V \subset Y$. Let $k=\left\lceil n^{1 / 2}\right\rceil$. Consider three events $\mathcal{A}, \mathcal{B}$ and $\mathcal{C}$, as follows.

  $$\begin{array}{ll} \mathcal{A}: & \text { there exist } U \subset X, V \subset Y \text { with }|U|=|V|=k \text { and } e(U, V)=0 \\ \mathcal{B}: & \text { there exist } x \in X, W \subset Y \text { with }|W|=n-k \text { and } e(\{x\}, W)=0 \\ \mathcal{C}: & \text { there exist } Z \subset X, y \in Y \text { with }|Z|=n-k \text { and } e(Z,\{y\})=0 \end{array}$$

  Show that $\operatorname{Pr}(\mathcal{A}) \leqslant n^{2 k}(1-p)^{k^{2}}$ and $\operatorname{Pr}(\mathcal{B} \cup \mathcal{C}) \leqslant 2 n^{k+1}(1-p)^{n-k}$. Hence show that $\operatorname{Pr}(\mathcal{A} \cup \mathcal{B} \cup \mathcal{C})<3 n^{2 k}(1-p)^{n / 2}$ and so show that, almost surely, none of $\mathcal{A}, \mathcal{B}$ or $\mathcal{C}$ occur. Deduce that, almost surely, $G$ has a matching from $X$ to $Y$.

  comment

• 4.II.17F

  Graph Theory

  Part II, 2005

  Write an essay on extremal graph theory. Your essay should include the proof of at least one extremal theorem. You should state the Erdős-Stone theorem, as well as describing its proof and showing how it can be applied.

  comment

• 1.II .17F

  Graph Theory

  Part II, 2006

  State and prove Euler's formula relating the number of vertices, edges and faces of a connected plane graph

  Deduce that a planar graph of order $n \geqslant 3$ has size at most $3 n-6$. What bound can be given if the planar graph contains no triangles?

  Without invoking the four colour theorem, prove that a planar graph that contains no triangles is 4-colourable.

  comment

• 2.II.17F

  Graph Theory

  Part II, 2006

  Let $G$ be a bipartite graph with vertex classes $X$ and $Y$. State Hall's necessary condition for $G$ to have a matching from $X$ to $Y$, and prove that it is sufficient.

  Deduce a necessary and sufficient condition for $G$ to have $|X|-d$ independent edges, where $d$ is a natural number.

  Show that the maximum size of a set of independent edges in $G$ is equal to the minimum size of a subset $S \subset V(G)$ such that every edge of $G$ has an end vertex in $S$.

  comment

• 3.II.17F

  Graph Theory

  Part II, 2006

  Let $R(s)$ be the least integer $n$ such that every colouring of the edges of $K_{n}$ with two colours contains a monochromatic $K_{s}$. Prove that $R(s)$ exists.

  Prove that a connected graph of maximum degree $d \geqslant 2$ and order $d^{k}$ contains two vertices distance at least $k$ apart.

  Let $C(s)$ be the least integer $n$ such that every connected graph of order $n$ contains, as an induced subgraph, either a complete graph $K_{s}$, a star $K_{1, s}$ or a path $P_{s}$ of length $s$. Show that $C(s) \leqslant R(s)^{s}$.

  comment

• 4.II.17F

  Graph Theory

  Part II, 2006

  What is meant by a graph $G$ of order $n$ being strongly regular with parameters $(d, a, b) ?$ Show that, if such a graph $G$ exists and $b>0$, then

  $$\frac{1}{2}\left\{n-1+\frac{(n-1)(b-a)-2 d}{\sqrt{(a-b)^{2}+4(d-b)}}\right\}$$

  is an integer.

  Let $G$ be a graph containing no triangles, in which every pair of non-adjacent vertices has exactly three common neighbours. Show that $G$ must be $d$-regular and $|G|=1+d(d+2) / 3$ for some $d \in\{1,3,21\}$. Show that such a graph exists for $d=3$.

  comment

• 1.II.17H

  Graph Theory

  Part II, 2007

  Let $G$ be a connected cubic graph drawn in the plane with each edge in the boundary of two distinct faces. Show that the associated map is 4 -colourable if and only if $G$ is 3 -edge colourable.

  Is the above statement true if the plane is replaced by the torus and all faces are required to be simply connected? Give a proof or a counterexample.

  comment

• 2.II.17H

  Graph Theory

  Part II, 2007

  The Ramsey number $R(G)$ of a graph $G$ is the smallest $n$ such that in any red/blue colouring of the edges of $K_{n}$ there is a monochromatic copy of $G$.

  Show that $R\left(K_{t}\right) \leqslant\left(\begin{array}{c}2 t-2 \\ t-1\end{array}\right)$ for every $t \geqslant 3$.

  Let $H$ be the graph on four vertices obtained by adding an edge to a triangle. Show that $R(H)=7$.

  comment

• 3.II.17H

  Graph Theory

  Part II, 2007

  Let $G$ be a bipartite graph with vertex classes $X$ and $Y$, each of size $n$. State and prove Hall's theorem giving a necessary and sufficient condition for $G$ to contain a perfect matching.

  A vertex $x \in X$ is flexible if every edge from $x$ is contained in a perfect matching. Show that if $|\Gamma(A)|>|A|$ for every subset $A$ of $X$ with $\emptyset \neq A \neq X$, then every $x \in X$ is flexible.

  Show that whenever $G$ contains a perfect matching, there is at least one flexible $x \in X$.

  Give an example of such a $G$ where no $x \in X$ of minimal degree is flexible.

  comment

• 4.II.17H

  Graph Theory

  Part II, 2007

  Let $G$ be a graph with $n$ vertices and $m$ edges. Show that if $G$ contains no $C_{4}$, then $m \leqslant \frac{n}{4}(1+\sqrt{4 n-3})$.

  Let $C_{4}(G)$ denote the number of subgraphs of $G$ isomorphic to $C_{4}$. Show that if $m \geqslant \frac{n(n-1)}{4}$, then $G$ contains at least $\frac{n(n-1)(n-3)}{8}$ paths of length 2 . By considering the numbers $r_{1}, r_{2}, \ldots, r_{\left(\begin{array}{c}n \\ 2\end{array}\right)}$ of vertices joined to each pair of vertices of $G$, deduce that

  $$C_{4}(G) \geqslant \frac{1}{2}\left(\begin{array}{l} n \\ 2 \end{array}\right)\left(\begin{array}{c} (n-3) / 4 \\ 2 \end{array}\right)$$

  Now let $G=G(n, 1 / 2)$ be the random graph on $\{1,2, \ldots, n\}$ in which each pair of vertices is joined independently with probability $1 / 2$. Find the expectation $\mathbb{E}\left(C_{4}(G)\right)$ of $C_{4}(G)$. Deduce that if $0<\epsilon<1 / 2$, then

  $$\operatorname{Pr}\left(C_{4}(G) \leqslant(1+2 \epsilon) \frac{3}{16}\left(\begin{array}{l} n \\ 4 \end{array}\right)\right) \geqslant \epsilon$$

  comment

• 1.II .17F

  Graph Theory

  Part II, 2008

  State a result of Euler concerning the number of vertices, edges and faces of a connected plane graph. Deduce that if $G$ is a planar graph then $\delta(G) \leqslant 5$. Show that if $G$ is a planar graph then $\chi(G) \leqslant 5$.

  Are the following statements true or false? Justify your answers.

  [You may quote standard facts about planar and non-planar graphs, provided that they are clearly stated.]

  (i) If $G$ is a graph with $\chi(G) \leqslant 4$ then $G$ is planar.

  (ii) If $G$ is a connected graph with average degree at most $2.01$ then $G$ is planar.

  (iii) If $G$ is a connected graph with average degree at most 2 then $G$ is planar.

  comment

• 2.II.17F

  Graph Theory

  Part II, 2008

  Prove that every graph $G$ on $n \geqslant 3$ vertices with minimum degree $\delta(G) \geqslant \frac{n}{2}$ is Hamiltonian. For each $n \geqslant 3$, give an example to show that this result does not remain true if we weaken the condition to $\delta(G) \geqslant \frac{n}{2}-1$ (for $n$ even) or $\delta(G) \geqslant \frac{n-1}{2}$ (for $n$ odd).

  For any graph $G$, let $G_{k}$ denote the graph formed by adding $k$ new vertices to $G$, all joined to each other and to all vertices of $G$. By considering $G_{1}$, show that if $G$ is a graph on $n \geqslant 3$ vertices with $\delta(G) \geqslant \frac{n-1}{2}$ then $G$ has a Hamilton path (a path passing through all the vertices of $G$ ).

  For each positive integer $k$, exhibit a connected graph $G$ such that $G_{k}$ is not Hamiltonian. Is this still possible if we replace 'connected' with '2-connected'?

  comment

• 3.II $. 17 \mathrm{~F} \quad$

  Graph Theory

  Part II, 2008

  Define the chromatic polynomial $p_{G}(t)$ of a graph $G$. Show that if $G$ has $n$ vertices and $m$ edges then

  $$p_{G}(t)=a_{n} t^{n}-a_{n-1} t^{n-1}+a_{n-2} t^{n-2}-\ldots+(-1)^{n} a_{0}$$

  where $a_{n}=1$ and $a_{n-1}=m$ and $a_{i} \geqslant 0$ for all $0 \leqslant i \leqslant n$. [You may assume the deletion-contraction relation, provided it is clearly stated.]

  Show that if $G$ is a tree on $n$ vertices then $p_{G}(t)=t(t-1)^{n-1}$. Does the converse hold?

  [Hint: if $G$ is disconnected, how is the chromatic polynomial of $G$ related to the chromatic polynomials of its components?]

  Show that if $G$ is a graph on $n$ vertices with the same chromatic polynomial as $T_{r}(n)$ (the Turán graph on $n$ vertices with $r$ vertex classes) then $G$ must be isomorphic to $T_{r}(n)$.

  comment

• 4.II.17F

  Graph Theory

  Part II, 2008

  For $s \geqslant 2$, let $R(s)$ be the least integer $n$ such that for every 2 -colouring of the edges of $K_{n}$ there is a monochromatic $K_{s}$. Prove that $R(s)$ exists.

  For any $k \geqslant 1$ and $s_{1}, \ldots, s_{k} \geqslant 2$, define the Ramsey number $R_{k}\left(s_{1}, \ldots, s_{k}\right)$, and prove that it exists.

  Show that, whenever the positive integers are partitioned into finitely many classes, some class contains $x, y, z$ with $x+y=z$.

  [Hint: given a finite colouring of the positive integers, induce a colouring of the pairs of positive integers by giving the pair $i j(i<j)$ the colour of $j-i$.]

  comment

• Paper 2, Section II, F

  Graph Theory

  Part II, 2009

  (i) Define the Turán graph $T_{r}(n)$. State and prove Turán's theorem.

  (ii) For each value of $n$ and $r$ with $n>r$, exhibit a graph $G$ on $n$ vertices that has fewer edges than $T_{r-1}(n)$ and yet is maximal $K_{r}$-free (meaning that $G$ contains no $K_{r}$ but the addition of any edge to $G$ produces a $K_{r}$ ). In the case $r=3$, determine the smallest number of edges that such a $G$ can have.

  comment

• Paper 1, Section II, $17 \mathrm{~F}$

  Graph Theory

  Part II, 2009

  (i) State and prove Hall's theorem concerning matchings in bipartite graphs.

  (ii) The matching number of a graph $G$ is the maximum size of a family of independent edges (edges without shared vertices) in $G$. Deduce from Hall's theorem that if $G$ is a $k$-regular bipartite graph on $n$ vertices (some $k>0$ ) then $G$ has matching number $n / 2$.

  (iii) Now suppose that $G$ is an arbitrary $k$-regular graph on $n$ vertices (some $k>0)$. Show that $G$ has a matching number at least $\frac{k}{4 k-2} n$. [Hint: Let $S$ be the set of vertices in a maximal set of independent edges. Consider the edges of $G$ with exactly one endpoint in $S$.]

  For $k=2$, show that there are infinitely many graphs $G$ for which equality holds.

  comment

• Paper 4, Section II, F

  Graph Theory

  Part II, 2009

  Let $X$ denote the number of triangles in a random graph $G$ chosen from $G(n, p)$. Find the mean and variance of $X$. Hence show that $p=n^{-1}$ is a threshold for the existence of a triangle, in the sense that if $p n \rightarrow 0$ then almost surely $G$ does not contain a triangle, while if $p n \rightarrow \infty$ then almost surely $G$ does contain a triangle.

  Now let $p=n^{-1 / 2}$, and let $Y$ denote the number of edges of $G$ (chosen as before from $G(n, p))$. By considering the mean of $Y-X$, show that for each $n \geqslant 3$ there exists a graph on $n$ vertices with at least $\frac{1}{6} n^{3 / 2}$ edges that is triangle-free. Is this within a constant factor of the best-possible answer (meaning the greatest number of edges that a triangle-free graph on $n$ vertices can have)?

  comment

• Paper 3, Section II, F

  Graph Theory

  Part II, 2009

  (a) State Brooks' theorem concerning the chromatic number $\chi(G)$ of a graph $G$. Prove it in the case when $G$ is 3-connected.

  [If you wish to assume that $G$ is regular, you should explain why this assumption is justified.]

  (b) State Vizing's theorem concerning the edge-chromatic number $\chi^{\prime}(G)$ of a graph $G$.

  (c) Are the following statements true or false? Justify your answers.

  (1) If $G$ is a connected graph on more than two vertices then $\chi(G) \leqslant \chi^{\prime}(G)$.

  (2) For every ordering of the vertices of a graph $G$, if we colour $G$ using the greedy algorithm (on this ordering) then the number of colours we use is at most $2 \chi(G)$.

  (3) For every ordering of the edges of a graph $G$, if we edge-colour $G$ using the greedy algorithm (on this ordering) then the number of colours we use is at most $2 \chi^{\prime}(G)$.

  comment

• Paper 1, Section II, F

  Graph Theory

  Part II, 2010

  (a) Define the Ramsey number $R(s)$. Show that for all integers $s \geqslant 2$ the Ramsey number $R(s)$ exists and that $R(s) \leqslant 4^{s}$.

  (b) For any graph $G$, let $R(G)$ denote the least positive integer $n$ such that in any red-blue colouring of the edges of the complete graph $K_{n}$ there must be a monochromatic copy of $G$.

  (i) How do we know that $R(G)$ exists for every graph $G$ ?

  (ii) Let $s$ be a positive integer. Show that, whenever the edge of $K_{2 s}$ are red-blue coloured, there must be a monochromatic copy of the complete bipartite graph $K_{1, s}$.

  (iii) Suppose $s$ is odd. By exhibiting a suitable colouring of $K_{2 s-1}$, show that $R\left(K_{1, s}\right)=2 s$.

  (iv) Suppose instead $s$ is even. What is $R\left(K_{1, s}\right) ?$ Justify your answer.

  comment

• Paper 2, Section II, F

  Graph Theory

  Part II, 2010

  Let $G$ be a bipartite graph with vertex classes $X$ and $Y$. What does it mean to say that $G$ contains a matching from $X$ to $Y$ ?

  State and prove Hall's Marriage Theorem, giving a necessary and sufficient condition for $G$ to contain a matching from $X$ to $Y$.

  Now assume that $G$ does contain a matching (from $X$ to $Y$ ). For a subset $A \subset X$, $\Gamma(A)$ denotes the set of vertices adjacent to some vertex in $A$.

  (i) Suppose $|\Gamma(A)|>|A|$ for every $A \subset X$ with $A \neq \emptyset, X$. Show that every edge of $G$ is contained in a matching.

  (ii) Suppose that every edge of $G$ is contained in a matching and that $G$ is connected. Show that $|\Gamma(A)|>|A|$ for every $A \subset X$ with $A \neq \emptyset, X$.

  (iii) For each $n \geqslant 2$, give an example of $G$ with $|X|=n$ such that every edge is contained in a matching but $|\Gamma(A)|=|A|$ for some $A \subset X$ with $A \neq \emptyset, X$.

  (iv) Suppose that every edge of $G$ is contained in a matching. Must every pair of independent edges in $G$ be contained in a matching? Give a proof or counterexample as appropriate.

  [No form of Menger's Theorem or of the Max-Flow-Min-Cut Theorem may be assumed without proof.]

  comment

• Paper 3, Section II, F

  Graph Theory

  Part II, 2010

  Let $G$ be a graph of order $n$. Show that $G$ must contain an independent set of $\left\lceil\sum_{v \in G} \frac{1}{d(v)+1}\right]$ vertices (where $\lceil x\rceil$ denotes the least integer $\left.\geqslant x\right)$.

  [Hint: take a random ordering of the vertices of $G$, and consider the set of those vertices which are adjacent to no earlier vertex in the ordering.]

  Fix an integer $m<n$ with $m$ dividing $n$, and suppose that $e(G)=m\left(\begin{array}{c}n / m \\ 2\end{array}\right)$.

  (i) Deduce that $G$ must contain an independent set of $m$ vertices.

  (ii) Must $G$ contain an independent set of $m+1$ vertices?

  comment

• Paper 4, Section II, F

  Graph Theory

  Part II, 2010

  State Euler's formula relating the number of vertices, edges and faces in a drawing of a connected planar graph. Deduce that every planar graph has chromatic number at most $5 .$

  Show also that any triangle-free planar graph has chromatic number at most 4 .

  Suppose $G$ is a planar graph which is minimal 5 -chromatic; that is to say, $\chi(G)=5$ but if $H$ is a subgraph of $G$ with $H \neq G$ then $\chi(H)<5$. Prove that $\delta(G) \geqslant 5$. Does this remain true if we drop the assumption that $G$ is planar? Justify your answer.

  [The Four Colour Theorem may not be assumed.]

  comment

• Paper 1, Section II, F

  Graph Theory

  Part II, 2011

  Let $G$ be a bipartite graph with vertex classes $X$ and $Y$. What is a matching from $X$ to $Y$ ?

  Show that if $|\Gamma(A)| \geqslant|A|$ for all $A \subset X$ then $G$ contains a matching from $X$ to $Y$.

  Let $d$ be a positive integer. Show that if $|\Gamma(A)| \geqslant|A|-d$ for all $A \subset X$ then $G$ contains a set of $|X|-d$ independent edges.

  Show that if 0 is not an eigenvalue of $G$ then $G$ contains a matching from $X$ to $Y$.

  Suppose now that $|X|=|Y| \geqslant 1$ and that $G$ does contain a matching from $X$ to $Y$. Must it be the case that 0 is not an eigenvalue of $G$ ? Justify your answer.

  comment

• Paper 2, Section II, F

  Graph Theory

  Part II, 2011

  What does it mean to say that a graph $G$ is $k$-colourable? Define the chromatic number $\chi(G)$ of a graph $G$, and the chromatic number $\chi(S)$ of a closed surface $S$.

  State the Euler-Poincaré formula relating the numbers of vertices, edges and faces in a drawing of a graph $G$ on a closed surface $S$ of Euler characteristic $E$. Show that if $E \leqslant 0$ then

  $$\chi(S) \leqslant\left[\frac{7+\sqrt{49-24 E}}{2}\right\rfloor$$

  Find, with justification, the chromatic number of the Klein bottle $N_{2}$. Show that if $G$ is a triangle-free graph which can be drawn on the Klein bottle then $\chi(G) \leqslant 4$.

  [You may assume that the Klein bottle has Euler characteristic 0 , and that $K_{6}$ can be drawn on the Klein bottle but $K_{7}$ cannot. You may use Brooks's theorem.]

  comment

• Paper 3, Section II, $17 \mathrm{~F}$

  Graph Theory

  Part II, 2011

  Define the Turán graph $T_{r}(n)$. State and prove Turán's theorem. Hence, or otherwise, find $\operatorname{ex}\left(K_{3} ; n\right)$.

  Let $G$ be a bipartite graph with $n$ vertices in each class. Let $k$ be an integer, $1 \leqslant k \leqslant n$, and assume $e(G)>(k-1) n$. Show that $G$ contains a set of $k$ independent edges.

  [Hint: Suppose $G$ contains a set $D$ of a independent edges but no set of a $+1$ independent edges. Let $U$ be the set of vertices of the edges in $D$ and let $F$ be the set of edges in $G$ with precisely one vertex in $U$; consider $|F| .]$

  Hence, or otherwise, show that if $H$ is a triangle-free tripartite graph with $n$ vertices in each class then $e(H) \leqslant 2 n^{2}$.

  comment

• Paper 4, Section II, F

  Graph Theory

  Part II, 2011

  (i) Given a positive integer $k$, show that there exists a positive integer $n$ such that, whenever the edges of the complete graph $K_{n}$ are coloured with $k$ colours, there exists a monochromatic triangle.

  Denote the least such $n$ by $f(k)$. Show that $f(k) \leqslant 3 \cdot k !$ for all $k$.

  (ii) You may now assume that $f(2)=6$ and $f(3)=17$.

  Let $H$ denote the graph of order 4 consisting of a triangle together with one extra edge. Given a positive integer $k$, let $g(k)$ denote the least positive integer $n$ such that, whenever the edges of the complete graph $K_{n}$ are coloured with $k$ colours, there exists a monochromatic copy of $H$. By considering the edges from one vertex of a monochromatic triangle in $K_{7}$, or otherwise, show that $g(2) \leqslant 7$. By exhibiting a blue-yellow colouring of the edges of $K_{6}$ with no monochromatic copy of $H$, show that in fact $g(2)=7$.

  What is $g(3) ?$ Justify your answer.

  comment

• Paper 4, Section II, F

  Graph Theory

  Part II, 2012

  (a) Show that every finite tree of order at least 2 has a leaf. Hence, or otherwise, show that a tree of order $n \geqslant 1$ must have precisely $n-1$ edges.

  (b) Let $G$ be a graph. Explain briefly why $|G| / \alpha(G) \leqslant \chi(G) \leqslant \Delta(G)+1$.

  Let $k=\chi(G)$, and assume $k \geqslant 2$. By induction on $|G|$, or otherwise, show that $G$ has a subgraph $H$ with $\delta(H) \geqslant k-1$. Hence, or otherwise, show that if $T$ is a tree of order $k$ then $T \subseteq G$.

  (c) Let $s, t \geqslant 2$ be integers, let $n=(s-1)(t-1)+1$ and let $T$ be a tree of order $t$. Show that whenever the edges of the complete graph $K_{n}$ are coloured blue and yellow then it must contain either a blue $K_{s}$ or a yellow $T$.

  Does this remain true if $K_{n}$ is replaced by $K_{n-1}$ ? Justify your answer.

  [The independence number $\alpha(G)$ of a graph $G$ is the size of the largest set $W \subseteq V(G)$ of vertices such that no edge of $G$ joins two points of $W$. Recall that $\chi(G)$ is the chromatic number and $\delta(G), \Delta(G)$ are respectively the minimal/maximal degrees of vertices in $G$.]

  comment

• Paper 3, Section II, $17 \mathrm{~F}$

  Graph Theory

  Part II, 2012

  Let $H$ be a graph with at least one edge. Define ex $(n ; H)$, where $n$ is an integer with $n \geqslant|H|$. Without assuming the Erdős-Stone theorem, show that the sequence $\operatorname{ex}(n ; H) /\left(\begin{array}{l}n \\ 2\end{array}\right)$ converges as $n \rightarrow \infty$.

  State precisely the Erdős-Stone theorem. Hence determine, with justification, $\lim _{n \rightarrow \infty} \operatorname{ex}(n ; H) /\left(\begin{array}{c}n \\ 2\end{array}\right) .$

  Let $K$ be another graph with at least one edge. For each integer $n$ such that $n \geqslant \max \{|H|,|K|\}$, let

  $$f(n)=\max \{e(G):|G|=n ; H \not \subset G \text { and } K \not \subset G\}$$

  and let

  $$g(n)=\max \{e(G):|G|=n ; H \not \subset G \text { or } K \not \subset G\} .$$

  Find, with justification, $\lim _{n \rightarrow \infty} f(n) /\left(\begin{array}{l}n \\ 2\end{array}\right)$ and $\lim _{n \rightarrow \infty} g(n) /\left(\begin{array}{l}n \\ 2\end{array}\right)$.

  comment

• Paper 2, Section II, F

  Graph Theory

  Part II, 2012

  Let $G$ be a $k$-connected graph $(k \geqslant 2)$. Let $v \in G$ and let $U \subset V(G) \backslash\{v\}$ with $|U| \geqslant k$. Show that $G$ contains $k$ paths from $v$ to $U$ with any two having only the vertex $v$ in common.

  [No form of Menger's theorem or of the Max-Flow-Min-Cut theorem may be assumed without proof.]

  Deduce that $G$ must contain a cycle of length at least $k$.

  Suppose further that $G$ has no independent set of vertices of size $>k$. Show that $G$ is Hamiltonian.

  [Hint. If not, let $C$ be a cycle of maximum length in $G$ and let $v \in V(G) \backslash V(C)$; consider the set of vertices on $C$ immediately preceding the endvertices of a collection of $k$ paths from $v$ to $C$ that have only the vertex $v$ in common.]

  comment

• Paper 1, Section II, F

  Graph Theory

  Part II, 2012

  State Markov's inequality and Chebyshev's inequality.

  Let $\mathcal{G}^{(2)}(n, p)$ denote the probability space of bipartite graphs with vertex classes $U=\{1,2, \ldots, n\}$ and $V=\{-1,-2, \ldots,-n\}$, with each possible edge $u v(u \in U,$, $v \in V)$ present, independently, with probability $p$. Let $X$ be the number of subgraphs of $G \in \mathcal{G}^{(2)}(n, p)$ that are isomorphic to the complete bipartite graph $K_{2,2}$. Write down $\mathbb{E} X$ and $\operatorname{Var}(X)$. Hence show that $p=1 / n$ is a threshold for $G \in \mathcal{G}^{(2)}(n, p)$ to contain $K_{2,2}$, in the sense that if $n p \rightarrow \infty$ then a. e. $G \in \mathcal{G}^{(2)}(n, p)$ contains a $K_{2,2}$, whereas if $n p \rightarrow 0$ then a. e. $G \in \mathcal{G}^{(2)}(n, p)$ does not contain a $K_{2,2}$.

  By modifying a random $G \in \mathcal{G}^{(2)}(n, p)$ for suitably chosen $p$, show that, for each $n$, there exists a bipartite graph $H$ with $n$ vertices in each class such that $K_{2,2} \not \subset H$ but $e(H) \geqslant \frac{3}{4}\left(\frac{n}{\sqrt[3]{n-1}}\right)^{2} .$

  comment

• Paper 4, Section II, F

  Graph Theory

  Part II, 2013

  Define the maximum degree $\Delta(G)$ and the chromatic index $\chi^{\prime}(G)$ of the graph $G$.

  State and prove Vizing's theorem relating $\Delta(G)$ and $\chi^{\prime}(G)$.

  Let $G$ be a connected graph such that $\chi^{\prime}(G)=\Delta(G)+1$ but, for every subgraph $H$ of $G, \chi^{\prime}(H)=\Delta(H)$ holds. Show that $G$ is a circuit of odd length.

  comment

• Paper 3, Section II, F

  Graph Theory

  Part II, 2013

  Let $G$ be a graph of order $n$ and average degree $d$. Let $A$ be the adjacency matrix of $G$ and let $x^{n}+c_{1} x^{n-1}+c_{2} x^{n-2}+\cdots+c_{n}$ be its characteristic polynomial. Show that $c_{1}=0$ and $c_{2}=-n d / 2$. Show also that $-c_{3}$ is twice the number of triangles in $G$.

  The eigenvalues of $A$ are $\lambda_{1} \geqslant \lambda_{2} \geqslant \cdots \geqslant \lambda_{n}$. Prove that $\lambda_{1} \geqslant d$.

  Evaluate $\lambda_{1}+\cdots+\lambda_{n}$. Show that $\lambda_{1}^{2}+\cdots+\lambda_{n}^{2}=n d$ and infer that $\lambda_{1} \leqslant \sqrt{d(n-1)}$. Does there exist, for each $n$, a graph $G$ with $d>0$ for which $\lambda_{2}=\cdots=\lambda_{n}$ ?

  comment

• Paper 2, Section II, F

  Graph Theory

  Part II, 2013

  Let $G$ be a graph with $|G| \geqslant 3$. State and prove a necessary and sufficient condition for $G$ to be Eulerian (that is, for $G$ to have an Eulerian circuit).

  Prove that if $\delta(G) \geqslant|G| / 2$ then $G$ is Hamiltonian (that is, $G$ has a Hamiltonian circuit).

  The line graph $L(G)$ of $G$ has vertex set $V(L(G))=E(G)$ and edge set

  $$E(L(G))=\{e f: e, f \in E(G), e \text { and } f \text { are incident }\} .$$

  Show that $L(G)$ is Eulerian if $G$ is regular and connected.

  Must $L(G)$ be Hamiltonian if $G$ is Eulerian? Must $G$ be Eulerian if $L(G)$ is Hamiltonian? Justify your answers.

  comment

• Paper 1, Section II, F

  Graph Theory

  Part II, 2013

  State and prove Hall's theorem about matchings in bipartite graphs.

  Show that a regular bipartite graph has a matching meeting every vertex.

  A graph is almost r-regular if each vertex has degree $r-1$ or $r$. Show that, if $r \geqslant 2$, an almost $r$-regular graph $G$ must contain an almost $(r-1)$-regular graph $H$ with $V(H)=V(G)$.

  [Hint: First, if possible, remove edges from $G$ whilst keeping it almost r-regular.]

  comment

• Paper 4, Section II, I

  Graph Theory

  Part II, 2014

  Define the Ramsey number $R^{(r)}(s, t)$. What is the value of $R^{(1)}(s, t)$ ? Prove that $R^{(r)}(s, t) \leqslant 1+R^{(r-1)}\left(R^{(r)}(s-1, t), R^{(r)}(s, t-1)\right)$ holds for $r \geqslant 2$ and deduce that $R^{(r)}(s, t)$ exists.

  Show that $R^{(2)}(3,3)=6$ and that $R^{(2)}(3,4)=9$.

  Show that $7 \leqslant R^{(3)}(4,4) \leqslant 19$. [Hint: For the lower bound, choose a suitable subset $U$ and colour e red if $|U \cap e|$ is odd.]

  comment

• Paper 3, Section II, I

  Graph Theory

  Part II, 2014

  Prove that $\chi(G) \leqslant \Delta(G)+1$ for every graph $G$. Prove further that, if $\kappa(G) \geqslant 3$, then $\chi(G) \leqslant \Delta(G)$ unless $G$ is complete.

  Let $k \geqslant 2$. A graph $G$ is said to be $k$-critical if $\chi(G)=k+1$, but $\chi(G-v)=k$ for every vertex $v$ of $G$. Show that, if $G$ is $k$-critical, then $\kappa(G) \geqslant 2$.

  Let $k \geqslant 2$, and let $H$ be the graph $K_{k+1}$ with an edge removed. Show that $H$ has the following property: it has two vertices which receive the same colour in every $k$-colouring of $H$. By considering two copies of $H$, construct a $k$-colourable graph $G$ of order $2 k+1$ with the following property: it has three vertices which receive the same colour in every $k$-colouring of $G$.

  Construct, for all integers $k \geqslant 2$ and $\ell \geqslant 2$, a $k$-critical graph $G$ of order $\ell k+1$ with $\kappa(G)=2 .$

  comment

• Paper 2, Section II, I

  Graph Theory

  Part II, 2014

  Let $k$ and $n$ be integers with $1 \leqslant k<n$. Show that every connected graph of order $n$, in which $d(u)+d(v) \geqslant k$ for every pair $u, v$ of non-adjacent vertices, contains a path of length $k$.

  Let $k$ and $n$ be integers with $1 \leqslant k \leqslant n$. Show that a graph of order $n$ that contains no path of length $k$ has at most $(k-1) n / 2$ edges, and that this value is achieved only if $k$ divides $n$ and $G$ is the union of $n / k$ disjoint copies of $K_{k}$. [Hint: Proceed by induction on $n$ and consider a vertex of minimum degree.]

  comment

• Paper 1, Section II, I

  Graph Theory

  Part II, 2014

  Show that a graph is bipartite if and only if all of its cycles are of even length.

  Show that a bridgeless plane graph is bipartite if and only if all of its faces are of even length.

  Let $G$ be an Eulerian plane graph. Show that the faces of $G$ can be coloured with two colours so that no two contiguous faces have the same colour. Deduce that it is possible to assign a direction to each edge of $G$ in such a way that the edges around each face form a directed cycle.

  comment

• Paper 1, Section II, I

  Graph Theory

  Part II, 2015

  (a) What does it mean to say that a graph $G$ is strongly regular with parameters $(k, a, b) ?$

  (b) Let $G$ be an incomplete, strongly regular graph with parameters $(k, a, b)$ and of order $n$. Suppose $b \geqslant 1$. Show that the numbers

  $$\frac{1}{2}\left(n-1 \pm \frac{(n-1)(b-a)-2 k}{\sqrt{(a-b)^{2}+4(k-b)}}\right)$$

  are integers.

  (c) Suppose now that $G$ is an incomplete, strongly regular graph with parameters $(k, 0,3)$. Show that $|G| \in\{6,162\}$.

  comment

• Paper 2, Section II, I

  Graph Theory

  Part II, 2015

  (a) Define the Ramsey numbers $R(s, t)$ and $R(s)$ for integers $s, t \geqslant 2$. Show that $R(s, t)$ exists for all $s, t \geqslant 2$ and that if $s, t \geqslant 3$ then $R(s, t) \leqslant R(s-1, t)+R(s, t-1)$.

  (b) Show that, as $s \rightarrow \infty$, we have $R(s)=O\left(4^{s}\right)$ and $R(s)=\Omega\left(2^{s / 2}\right)$.

  (c) Show that, as $t \rightarrow \infty$, we have $R(3, t)=O\left(t^{2}\right)$ and $R(3, t)=\Omega\left(\left(\frac{t}{\log t}\right)^{3 / 2}\right)$.

  [Hint: For the lower bound in (c), you may wish to begin by modifying a random graph to show that for all $n$ and $p$ we have

  $$R(3, t)>n-\left(\begin{array}{l} n \\ 3 \end{array}\right) p^{3}-\left(\begin{array}{c} n \\ t \end{array}\right)(1-p)\left(\begin{array}{c} t \\ 2 \end{array}\right)$$

  comment

• Paper 3, Section II, I

  Graph Theory

  Part II, 2015

  (a) Let $G$ be a graph. What is a Hamilton cycle in $G$ ? What does it mean to say that $G$ is Hamiltonian?

  (b) Let $G$ be a graph of order $n \geqslant 3$ satisfying $\delta(G) \geqslant \frac{n}{2}$. Show that $G$ is Hamiltonian. For each $n \geqslant 3$, exhibit a non-Hamiltonian graph $G_{n}$ of order $n$ with $\delta\left(G_{n}\right)=\left\lceil\frac{n}{2}\right\rceil-1$.

  (c) Let $H$ be a bipartite graph with $n \geqslant 2$ vertices in each class satisfying $\delta(H)>\frac{n}{2}$. Show that $H$ is Hamiltonian. For each $n \geqslant 2$, exhibit a non-Hamiltonian bipartite graph $H_{n}$ with $n$ vertices in each class and $\delta\left(H_{n}\right)=\left\lfloor\frac{n}{2}\right\rfloor$.

  comment

• Paper 4, Section II, I

  Graph Theory

  Part II, 2015

  Let $G$ be a bipartite graph with vertex classes $X$ and $Y$. What does it mean to say that $G$ contains a matching from $X$ to $Y$ ? State and prove Hall's Marriage Theorem.

  Suppose now that every $x \in X$ has $d(x) \geqslant 1$, and that if $x \in X$ and $y \in Y$ with $x y \in E(G)$ then $d(x) \geqslant d(y)$. Show that $G$ contains a matching from $X$ to $Y$.

  comment

• Paper 3, Section II, G

  Graph Theory

  Part II, 2016

  Define the chromatic polynomial $p_{G}(t)$ of a graph $G$. Show that if $G$ has $n$ vertices and $m$ edges then

  $$p_{G}(t)=a_{n} t^{n}-a_{n-1} t^{n-1}+a_{n-2} t^{n-2}-\ldots+(-1)^{n} a_{0}$$

  where $a_{n}=1, a_{n-1}=m$ and $a_{i} \geqslant 0$ for all $i$. [You may assume the deletion-contraction relation, provided that you state it clearly.]

  Show that for every graph $G$ (with $n>0$ ) we have $a_{0}=0$. Show also that $a_{1}=0$ if and only if $G$ is disconnected.

  Explain why $t^{4}-2 t^{3}+3 t^{2}-t$ is not the chromatic polynomial of any graph.

  comment

• Paper 2, Section II, G

  Graph Theory

  Part II, 2016

  Define the Turán graph $T_{r}(n)$, where $r$ and $n$ are positive integers with $n \geqslant r$. For which $r$ and $n$ is $T_{r}(n)$ regular? For which $r$ and $n$ does $T_{r}(n)$ contain $T_{4}(8)$ as a subgraph?

  State and prove Turán's theorem.

  Let $x_{1}, \ldots, x_{n}$ be unit vectors in the plane. Prove that the number of pairs $i<j$ for which $x_{i}+x_{j}$ has length less than 1 is at most $\left\lfloor n^{2} / 4\right\rfloor$.

  comment

• Paper 4, Section II, G

  Graph Theory

  Part II, 2016

  State Menger's theorem in both the vertex form and the edge form. Explain briefly how the edge form of Menger's theorem may be deduced from the vertex form.

  (a) Show that if $G$ is 3 -connected then $G$ contains a cycle of even length.

  (b) Let $G$ be a connected graph with all degrees even. Prove that $\lambda(G)$ is even. [Hint: if $S$ is a minimal set of edges whose removal disconnects $G$, let $H$ be a component of $G-S$ and consider the degrees of the vertices of $H$ in the graph $G-S$.] Give an example to show that $\kappa(G)$ can be odd.

  comment

• Paper 1, Section II, 16G

  Graph Theory

  Part II, 2016

  (a) Show that if $G$ is a planar graph then $\chi(G) \leqslant 5$. [You may assume Euler's formula, provided that you state it precisely.]

  (b) (i) Prove that if $G$ is a triangle-free planar graph then $\chi(G) \leqslant 4$.

  (ii) Prove that if $G$ is a planar graph of girth at least 6 then $\chi(G) \leqslant 3$.

  (iii) Does there exist a constant $g$ such that, if $G$ is a planar graph of girth at least $g$, then $\chi(G) \leqslant 2 ?$ Justify your answer.

  comment

• Paper 3, Section II, H

  Graph Theory

  Part II, 2017

  Define the Ramsey numbers $R(s, t)$ for integers $s, t \geqslant 2$. Show that $R(s, t)$ exists for all $s, t \geqslant 2$. Show also that $R(s, s) \leqslant 4^{s}$ for all $s \geqslant 2$.

  Let $t \geqslant 2$ be fixed. Give a red-blue colouring of the edges of $K_{2 t-2}$ for which there is no red $K_{t}$ and no blue odd cycle. Show, however, that for any red-blue colouring of the edges of $K_{2 t-1}$ there must exist either a red $K_{t}$ or a blue odd cycle.

  comment

• Paper 2, Section II, H

  Graph Theory

  Part II, 2017

  State and prove Hall's theorem about matchings in bipartite graphs.

  Let $A=\left(a_{i j}\right)$ be an $n \times n$ matrix, with all entries non-negative reals, such that every row sum and every column sum is 1. By applying Hall's theorem, show that there is a permutation $\sigma$ of $\{1, \ldots, n\}$ such that $a_{i \sigma(i)}>0$ for all $i$.

  comment

• Paper 1, Section II, H

  Graph Theory

  Part II, 2017

  Let $G$ be a graph of order $n \geqslant 3$ satisfying $\delta(G) \geqslant \frac{n}{2}$. Show that $G$ is Hamiltonian.

  Give an example of a planar graph $G$, with $\chi(G)=4$, that is Hamiltonian, and also an example of a planar graph $G$, with $\chi(G)=4$, that is not Hamiltonian.

  Let $G$ be a planar graph with the property that the boundary of the unbounded face is a Hamilton cycle of $G$. Prove that $\chi(G) \leqslant 3$.

  comment

• Paper 4, Section II, H

  Graph Theory

  Part II, 2017

  Let $G$ be a graph of maximum degree $\Delta$. Show the following:

  (i) Every eigenvalue $\lambda$ of $G$ satisfies $|\lambda| \leqslant \Delta$.

  (ii) If $G$ is regular then $\Delta$ is an eigenvalue.

  (iii) If $G$ is regular and connected then the multiplicity of $\Delta$ as an eigenvalue is 1 .

  (iv) If $G$ is regular and not connected then the multiplicity of $\Delta$ as an eigenvalue is greater than 1 .

  Let $A$ be the adjacency matrix of the Petersen graph. Explain why $A^{2}+A-2 I=J$, where $I$ is the identity matrix and $J$ is the all-1 matrix. Find, with multiplicities, the eigenvalues of the Petersen graph.

  comment

• Paper 4, Section II, I

  Graph Theory

  Part II, 2018

  Let $s \geqslant 3$. Define the Ramsey number $R(s)$. Show that $R(s)$ exists and that $R(s) \leqslant 4^{s}$.

  Show that $R(3)=6$. Show that (up to relabelling the vertices) there is a unique way to colour the edges of the complete graph $K_{5}$ blue and yellow with no monochromatic triangle.

  What is the least positive integer $n$ such that the edges of the complete graph $K_{6}$ can be coloured blue and yellow in such a way that there are precisely $n$ monochromatic triangles?

  comment

• Paper 3, Section II, I

  Graph Theory

  Part II, 2018

  What does it mean to say that a graph $G$ has a $k$-colouring? What are the chromatic number $\chi(G)$ and the independence number $\alpha(G)$ of a graph $G$ ? For each $r \geqslant 3$, give an example of a graph $G$ such that $\chi(G)>r$ but $K_{r} \not \subset G$.

  Let $g, k \geqslant 3$. Show that there exists a graph $G$ containing no cycle of length $\leqslant g$ with $\chi(G) \geqslant k$.

  Show also that if $n$ is sufficiently large then there is a triangle-free $G$ of order $n$ with $\alpha(G)<n^{0.7}$.

  comment

• Paper 2, Section II, I

  Graph Theory

  Part II, 2018

  Let $G$ be a graph and $A, B \subset V(G)$. Show that if every $A B$-separator in $G$ has order at least $k$ then there exist $k$ vertex-disjoint $A B$-paths in $G$.

  Let $k \geqslant 3$ and assume that $G$ is $k$-connected. Show that $G$ must contain a cycle of length at least $k$.

  Assume further that $|G| \geqslant 2 k$. Must $G$ contain a cycle of length at least $2 k ?$ Justify your answer.

  What is the largest integer $n$ such that any 3-connected graph $G$ with $|G| \geqslant n$ must contain a cycle of length at least $n$ ?

  [No form of Menger's theorem or of the max-flow-min-cut theorem may be assumed without proof.]

  comment

• Paper 1, Section II, I

  Graph Theory

  Part II, 2018

  (a) Define ex $(n, H)$ where $H$ is a graph with at least one edge and $n \geqslant|H|$. Show that, for any such $H$, the $\operatorname{limit}_{n \rightarrow \infty} \lim (n, H) /\left(\begin{array}{c}n \\ 2\end{array}\right)$ exists.

  [You may not assume the Erdős-Stone theorem.]

  (b) State the Erdős-Stone theorem. Use it to deduce that if $H$ is bipartite then $\lim _{n \rightarrow \infty} \operatorname{ex}(n, H) /\left(\begin{array}{l}n \\ 2\end{array}\right)=0 .$

  (c) Let $t \geqslant 2$. Show that ex $\left(n, K_{t, t}\right)=O\left(n^{2-\frac{1}{t}}\right)$.

  We say $A \subset \mathbb{Z}_{n}$ is nice if whenever $a, b, c, d \in A$ with $a+b=c+d$ then either $a=c, b=d$ or $a=d, b=c$. Let $f(n)=\max \left\{|A|: A \subset \mathbb{Z}_{n}, A\right.$ is nice $\}$. Show that $f(n)=O(\sqrt{n}) .$

  $\left[\mathbb{Z}_{n}\right.$ denotes the set of integers modulo $n$, i.e. $\mathbb{Z}_{n}=\{0,1,2, \ldots, n-1\}$ with addition modulo $n .]$

  comment

• Paper 4, Section II, G

  Graph Theory

  Part II, 2019

  State and prove Hall's theorem.

  Let $n$ be an even positive integer. Let $X=\{A: A \subset[n]\}$ be the power set of $[n]=\{1,2, \ldots, n\}$. For $1 \leqslant i \leqslant n$, let $X_{i}=\{A \in X:|A|=i\}$. Let $Q$ be the graph with vertex set $X$ where $A, B \in X$ are adjacent if and only if $|A \triangle B|=1$. [Here, $A \triangle B$ denotes the symmetric difference of $A$ and $B$, given by $A \triangle B:=(A \cup B) \backslash(A \cap B) .]$

  Let $1 \leqslant i \leqslant \frac{n}{2}$. Why is the induced subgraph $Q\left[X_{i} \cup X_{i-1}\right]$ bipartite? Show that it contains a matching from $X_{i-1}$ to $X_{i}$.

  A chain in $X$ is a subset $\mathcal{C} \subset X$ such that whenever $A, B \in \mathcal{C}$ we have $A \subset B$ or $B \subset A$. What is the least positive integer $k$ such that $X$ can be partitioned into $k$ pairwise disjoint chains? Justify your answer.

  comment

• Paper 3, Section II, G

  Graph Theory

  Part II, 2019

  (a) What does it mean to say that a graph is bipartite?

  (b) Show that $G$ is bipartite if and only if it contains no cycles of odd length.

  (c) Show that if $G$ is bipartite then

  $$\frac{\operatorname{ex}(n ; G)}{\left(\begin{array}{l} n \\ 2 \end{array}\right)} \rightarrow 0$$

  as $n \rightarrow \infty$.

  [You may use without proof the Erdós-Stone theorem provided it is stated precisely.]

  (d) Let $G$ be a graph of order $n$ with $m$ edges. Let $U$ be a random subset of $V(G)$ containing each vertex of $G$ independently with probability $\frac{1}{2}$. Let $X$ be the number of edges with precisely one vertex in $U$. Find, with justification, $\mathbb{E}(X)$, and deduce that $G$ contains a bipartite subgraph with at least $\frac{m}{2}$ edges.

  By using another method of choosing a random subset of $V(G)$, or otherwise, show that if $n$ is even then $G$ contains a bipartite subgraph with at least $\frac{m n}{2(n-1)}$ edges.

  comment

• Paper 2, Section II, 17G

  Graph Theory

  Part II, 2019

  (a) Suppose that the edges of the complete graph $K_{6}$ are coloured blue and yellow. Show that it must contain a monochromatic triangle. Does this remain true if $K_{6}$ is replaced by $K_{5}$ ?

  (b) Let $t \geqslant 1$. Suppose that the edges of the complete graph $K_{3 t-1}$ are coloured blue and yellow. Show that it must contain $t$ edges of the same colour with no two sharing a vertex. Is there any $t \geqslant 1$ for which this remains true if $K_{3 t-1}$ is replaced by $K_{3 t-2}$ ?

  (c) Now let $t \geqslant 2$. Suppose that the edges of the complete graph $K_{n}$ are coloured blue and yellow in such a way that there are a blue triangle and a yellow triangle with no vertices in common. Show that there are also a blue triangle and a yellow triangle that do have a vertex in common. Hence, or otherwise, show that whenever the edges of the complete graph $K_{5 t}$ are coloured blue and yellow it must contain $t$ monochromatic triangles, all of the same colour, with no two sharing a vertex. Is there any $t \geqslant 2$ for which this remains true if $K_{5 t}$ is replaced by $K_{5 t-1}$ ? [You may assume that whenever the edges of the complete graph $K_{10}$ are coloured blue and yellow it must contain two monochromatic triangles of the same colour with no vertices in common.]

  comment

• Paper 1, Section II, 17G

  Graph Theory

  Part II, 2019

  Let $G$ be a connected $d$-regular graph.

  (a) Show that $d$ is an eigenvalue of $G$ with multiplicity 1 and eigenvector

  $$e=(11 \ldots 1)^{T}$$

  (b) Suppose that $G$ is strongly regular. Show that $G$ has at most three distinct eigenvalues.

  (c) Conversely, suppose that $G$ has precisely three distinct eigenvalues $d, \lambda$ and $\mu$. Let $A$ be the adjacency matrix of $G$ and let

  $$B=A^{2}-(\lambda+\mu) A+\lambda \mu I .$$

  Show that if $v$ is an eigenvector of $G$ that is not a scalar multiple of $e$ then $B v=0$. Deduce that $B$ is a scalar multiple of the matrix $J$ whose entries are all equal to one. Hence show that, for $i \neq j,\left(A^{2}\right)_{i j}$ depends only on whether or not vertices $i$ and $j$ are adjacent, and so $G$ is strongly regular.

  (d) Which connected $d$-regular graphs have precisely two eigenvalues? Justify your answer.

  comment

• Paper 1, Section II, 17G

  Graph Theory

  Part II, 2020

  (a) The complement of a graph is defined as having the same vertex set as the graph, with vertices being adjacent in the complement if and only if they are not adjacent in the graph.

  Show that no planar graph of order greater than 10 has a planar complement.

  What is the maximum order of a bipartite graph that has a bipartite complement?

  (b) For the remainder of this question, let $G$ be a connected bridgeless planar graph with $n \geqslant 4$ vertices, $e$ edges, and containing no circuit of length 4 . Suppose that it is drawn with $f$ faces, of which $t$ are 3-sided.

  Show that $2 e \geqslant 3 t+5(f-t)$. Show further that $e \geqslant 3 t$, and hence $f \leqslant 8 e / 15$.

  Deduce that $e \leqslant 15(n-2) / 7$. Is there some $n$ and some $G$ for which equality holds? [Hint: consider "slicing the corners off" a dodecahedron.]

  comment

• Paper 2, Section II, 17G

  Graph Theory

  Part II, 2020

  (i) Define the local connectivity $\kappa(a, b ; G)$ for two non-adjacent vertices $a$ and $b$ in a graph $G$. Prove Menger's theorem, that $G$ contains a set of $\kappa(a, b ; G)$ vertex-disjoint $a-b$ paths.

  (ii) Recall that a subdivision $T K_{r}$ of $K_{r}$ is any graph obtained from $K_{r}$ by replacing its edges by vertex-disjoint paths. Let $G$ be a 3 -connected graph. Show that $G$ contains a $T K_{3}$. Show further that $G$ contains a $T K_{4}$. Must $G$ contain a $T K_{5}$?

  comment

• Paper 3, Section II, $17 \mathrm{G}$

  Graph Theory

  Part II, 2020

  (i) State and prove Turán's theorem.

  (ii) Let $G$ be a graph of order $2 n \geqslant 4$ with $n^{2}+1$ edges. Show that $G$ must contain a triangle, and that if $n=2$ then $G$ contains two triangles.

  (iii) Show that if every edge of $G$ lies in a triangle then $G$ contains at least $\left(n^{2}+1\right) / 3$ triangles.

  (iv) Suppose that $G$ has some edge $u v$ contained in no triangles. Show that $\Gamma(u) \cap \Gamma(v)=\emptyset$, and that if $|\Gamma(u)|+|\Gamma(v)|=2 n$ then $\Gamma(u)$ and $\Gamma(v)$ are not both independent sets.

  By induction on $n$, or otherwise, show that every graph of order $2 n \geqslant 4$ with $n^{2}+1$ edges contains at least $n$ triangles. [Hint: If uv is an edge that is contained in no triangles, consider $G-u-v$.]

  comment

• Paper 4 , Section II, $17 G$

  Graph Theory

  Part II, 2020

  State and prove Vizing's theorem about the chromatic index $\chi^{\prime}(G)$ of a graph $G$.

  Let $K_{m, n}$ be the complete bipartite graph with class sizes $m$ and $n$. By first considering $\chi^{\prime}\left(K_{n, n}\right)$, find $\chi^{\prime}\left(K_{m, n}\right)$ for all $m$ and $n$.

  Let $G$ be the graph of order $2 n+1$ obtained by subdividing a single edge of $K_{n, n}$ by a new vertex. Show that $\chi^{\prime}(G)=\Delta(G)+1$, where $\Delta(G)$ is the maximum degree of $G$.

  comment

• Paper 1, Section II, 17G

  Graph Theory

  Part II, 2021

  Define the binomial random graph $G(n, p)$, where $n \in \mathbb{N}$ and $p \in(0,1)$.

  (a) Let $G_{n} \sim G(n, p)$ and let $E_{t}$ be the event that $G_{n}$ contains a copy of the complete graph $K_{t}$. Show that if $p=p(n)$ is such that $p \cdot n^{2 /(t-1)} \rightarrow 0$ then $\mathbb{P}\left(E_{t}\right) \rightarrow 0$ as $n \rightarrow \infty$.

  (b) State Chebyshev's inequality. Show that if $p \cdot n \rightarrow \infty$ then $\mathbb{P}\left(E_{3}\right) \rightarrow 1$.

  (c) Let $H$ be a triangle with an added leaf vertex, that is

  $$H=\left(\left\{x_{1}, \ldots, x_{4}\right\},\left\{x_{1} x_{2}, x_{2} x_{3}, x_{3} x_{1}, x_{1} x_{4}\right\}\right),$$

  where $x_{1}, \ldots, x_{4}$ are distinct. Let $F$ be the event that $G_{n} \sim G(n, p)$ contains a copy of $H$. Show that if $p=n^{-0.9}$ then $\mathbb{P}(F) \rightarrow 1$.

  comment

• Paper 2, Section II, 17 G

  Graph Theory

  Part II, 2021

  (a) Define a tree and what it means for a graph to be acyclic. Show that if $G$ is an acyclic graph on $n$ vertices then $e(G) \leqslant n-1$. [You may use the fact that a spanning tree on $n$ vertices has $n-1$ edges.]

  (b) Show that any 3-regular graph on $n$ vertices contains a cycle of length $\leqslant$ $100 \log n$. Hence show that there exists $n_{0}$ such that every 3-regular graph on more than $n_{0}$ vertices must contain two cycles $C_{1}, C_{2}$ with disjoint vertex sets.

  (c) An unfriendly partition of a graph $G=(V, E)$ is a partition $V=A \cup B$, where $A, B \neq \emptyset$, such that every vertex $v \in A$ has $|N(v) \cap B| \geqslant|N(v) \cap A|$ and every $v \in B$ has $|N(v) \cap A| \geqslant|N(v) \cap B|$. Show that every graph $G$ with $|G| \geqslant 2$ has an unfriendly partition.

  (d) A friendly partition of a graph $G=(V, E)$ is a partition $V=S \cup T$, where $S, T \neq \emptyset$, such that every vertex $v \in S$ has $|N(v) \cap S| \geqslant|N(v) \cap T|$ and every $v \in T$ has $|N(v) \cap T| \geqslant|N(v) \cap S|$. Give an example of a 3-regular graph (on at least 1 vertex) that does not have a friendly partition. Using part (b), show that for large enough $n_{0}$ every 3-regular graph $G$ with $|G| \geqslant n_{0}$ has a friendly partition.

  comment

• Paper 3, Section II, 17G

  Graph Theory

  Part II, 2021

  (a) Define the Ramsey number $R(k)$ and show that $R(k) \leqslant 4^{k}$.

  Show that every 2-coloured complete graph $K_{n}$ with $n \geqslant 2$ contains a monochromatic spanning tree. Is the same true if $K_{n}$ is coloured with 3 colours? Give a proof or counterexample.

  (b) Let $G=(V, E)$ be a graph. Show that the number of paths of length 2 in $G$ is

  $$\sum_{x \in V} d(x)(d(x)-1) .$$

  Now consider a 2-coloured complete graph $K_{n}$ with $n \geqslant 3$. Show that the number of monochromatic triangles in $K_{n}$ is

  $$\frac{1}{2} \sum_{x}\left\{\left(\begin{array}{c} d_{r}(x) \\ 2 \end{array}\right)+\left(\begin{array}{c} d_{b}(x) \\ 2 \end{array}\right)\right\}-\frac{1}{2}\left(\begin{array}{l} n \\ 3 \end{array}\right)$$

  where $d_{r}(x)$ denotes the number of red edges incident with a vertex $x$ and $d_{b}(x)=$ $(n-1)-d_{r}(x)$ denotes the number of blue edges incident with $x$. [Hint: Count paths of length 2 in two different ways.]

  comment

• Paper 4, Section II, 17G

  Graph Theory

  Part II, 2021

  State and prove Hall's theorem, giving any definitions required by the proof (e.g. of an $M$-alternating path).

  Let $G=(V, E)$ be a (not necessarily bipartite) graph, and let $\gamma(G)$ be the size of the largest matching in $G$. Let $\beta(G)$ be the smallest $k$ for which there exist $k$ vertices $v_{1}, \ldots, v_{k} \in V$ such that every edge in $G$ is incident with at least one of $v_{1}, \ldots, v_{k}$. Show that $\gamma(G) \leqslant \beta(G)$ and that $\beta(G) \leqslant 2 \gamma(G)$. For each positive integer $k$, find a graph $G$ with $\beta(G)=2 k$ and $\gamma(G)=k$. Determine $\beta(G)$ and $\gamma(G)$ when $G$ is the Turan graph $T_{3}(30)$ on 30 vertices.

  By using Hall's theorem, or otherwise, show that if $G$ is a bipartite graph then $\gamma(G)=\beta(G) .$

  Define the chromatic index $\chi^{\prime}(G)$ of a graph $G$. Prove that if $n=2^{r}$ with $r \geqslant 1$ then $\chi^{\prime}\left(K_{n}\right)=n-1$.

  comment